‘Orthogonal arrays’ is a fairly recent mathematical theory that is attracting increasing interest. It concerns the
mathematical properties in the combining of factors, so-called “Combinatorics”. It has countless interesting
applications in science, industry and… testing.
Combinations are also employed in testing. Consider that system behaviour in general is determined by several
parameters, each of which can assume various values. In order to create a test case, the tester chooses one of the
possible values for each parameter. In fact, he is creating a combination of parameter values that is going to be
tested. The testing of all the possible combinations soon becomes unfeasible in practice. If, for example, there are 8
parameters, each of which have 3 possible values (or equivalence classes), then there are already 38 = 6,561
possibilities! Of necessity, only a subset can be tested. But what is a sensible subset to use? This is where
orthogonal arrays and pairwise testing can offer a solution.
This guideline first explains the principle of pairwise testing, to familiarise the reader with the meaning and
result of such techniques that are based on combinatorics. Subsequently, the more complex material of orthogonal arrays
is explained along general lines. The latter is not necessary in order to be able to apply the basic technique of
pairwise testing, but is intended for those interested in deeper theory.
PAIRWISE TESTING
Pairwise testing is based on the phenomenon that most faults in software are the consequence of one particular
factor or the combination of 2 factors. The number of faults that are caused by a specific combination of more than 2
factors becomes exponentially smaller. Instead of testing all the possible combinations of all the factors, it is very
effective if every combination of 2 factors is tested.
This delivers an enormous reduction in the number of required test cases, yet still gives a good fault-detection
result. The following example illustrates the meaning of pairwise testing.
In the system under test (for ordering books via the Internet), the following 3 parameters play a role. For each
parameter, there are 2 equivalence classes to be tested:
In order to test all the combinations relating to these 3 parameters, 2x2x2=8 test cases are required, namely:
|
Number of books
|
Sum
|
Membership card
|
|
1
|
Few
|
Low
|
None
|
|
2
|
Few
|
Low
|
Gold card
|
|
3
|
Few
|
High
|
None
|
|
4
|
Few
|
High
|
Gold card
|
|
5
|
Many
|
Low
|
None
|
|
6
|
Many
|
Low
|
Gold card
|
|
7
|
Many
|
High
|
None
|
|
8
|
Many
|
High
|
Gold card
|
For pairwise testing, as few as 4 test cases will suffice,
as shown below:
|
Number of books
|
Sum
|
Membership card
|
|
1
|
Few
|
Low
|
None
|
|
2
|
Few
|
High
|
Gold card
|
|
3
|
Many
|
Low
|
Gold card
|
|
4
|
Many
|
High
|
None
|
Of the 2 parameters [Number of books, Sum], all 4 existing
combinations are tested (Few/Low; Few/High; Many/Low; Many/High). The same applies to the other combinations of 2
parameters, so for [Number of books, Membership card] and [Sum, Membership card]. Check it for yourself.
What is the point of this? If a fault exists in the system that occurs when one of the possible values of one of the
parameters is combined with a particular value of one of the other parameters, then this fault is always found with
these 4 test cases. That is the strength of pairwise testing.
Deriving test cases for pairwise testing
If there is a pair of parameters with only 2 equivalence classes, the test cases necessary for pairwise testing can be
derived manually. In most situations in practice, however, there are more parameters and equivalence classes and it is
not possible to do this manually. In that case, there are 2 ways of solving this:
-
Application of orthogonal arrays (see following subsection)
-
Use of tools (discussed further in this section).
The number of necessary test cases, and how exactly they are combined, depends on the tool that is used. Various tools
are available, both commercially and free via the Internet (freeware). In the example below, the result of 2 freeware
tools is described.
Example - Take, for example, the following more extended version of the “book-ordering
system”. The previously mentioned parameters now have more equivalence classes, and another parameter: “Ordering
period”, has been added:
|
Number of books
|
1; 2-8; >8
|
|
Sum
|
<100; 100-250; >250
|
|
Membership card
|
None; Silver; Gold; Platinum
|
|
Ordering period
|
Weekday; Weekend; Public
holiday
|
For the testing of all possible combinations in this case, 3x3x4x3=108 test cases are necessary. For pairwise testing, a
fraction of these will suffice. Below, the results are shown that were obtained with 2 freeware tools:
Results with tool “Pict33”
This is a tool from Microsoft® and can be downloaded via their site or via www.pairwise.org/ . This tool generates the following 14 test cases:
|
Number of books
|
Sum
|
Membership card
|
Ordering period
|
|
1
|
1
|
<100
|
None
|
Public holiday
|
|
2
|
1
|
>250
|
Platinum
|
Weekday
|
|
3
|
1
|
>250
|
Silver
|
Weekday
|
|
4
|
1
|
100-250
|
Gold
|
Weekend
|
|
5
|
>8
|
<100
|
Silver
|
Weekend
|
|
6
|
>8
|
>250
|
None
|
Weekday
|
|
7
|
>8
|
>250
|
Gold
|
Public holiday
|
|
8
|
>8
|
100-250
|
Platinum
|
Public holiday
|
|
9
|
>8
|
100-250
|
Platinum
|
Weekday
|
|
10
|
2-8
|
<100
|
Platinum
|
Weekday
|
|
11
|
2-8
|
<100
|
Gold
|
Weekday
|
|
12
|
2-8
|
>250
|
Platinum
|
Weekend
|
|
13
|
2-8
|
100-250
|
Silver
|
Public holiday
|
|
14
|
2-8
|
100-250
|
None
|
Weekend
|
Result with “Allpairs” tool
The creator of this tool is James Bach. It may be downloaded from www.satisfice.com/. This tool generates the following 13 test cases:
|
Number of books
|
Sum
|
Membership card
|
Ordering period
|
|
1
|
1
|
<100
|
None
|
Weekday
|
|
2
|
2-8
|
100-250
|
None
|
Weekend
|
|
3
|
>8
|
>250
|
None
|
Public holiday
|
|
4
|
1
|
100-250
|
Silver
|
Public holiday
|
|
5
|
2-8
|
<100
|
Silver
|
Weekday
|
|
6
|
>8
|
<100
|
Silver
|
Weekend
|
|
7
|
1
|
>250
|
Gold
|
Weekend
|
|
8
|
2-8
|
<100
|
Gold
|
Public holiday
|
|
9
|
>8
|
100-250
|
Gold
|
Weekday
|
|
10
|
2-8
|
>250
|
Platinum
|
Weekday
|
|
11
|
1
|
<100
|
Platinum
|
Weekend
|
|
12
|
>8
|
100-250
|
Platinum
|
Public holiday
|
|
13
|
~1
|
>250
|
Silver
|
~Weekday
|
The symbol “~” in the last test case means that the value makes no difference here. A different equivalence class might
have been selected. The test case is solely required to complete the coverage of the other parameters.
Stronger variants, such as triplewise testing
The principle of pairwise testing can be extended to the combination of more than two factors. For example, the testing
of all the possibilities of any three random factors is known as ‘triplewise testing’. A general definition is as
follows: "N-wise testing has the aim of testing all the possibilities of any random combination of N
factors."
The maximum value for N is equal to the number of parameters. In that case, the result is equal to the testing of the
complete decision table: all the combinations of all the values of all the parameters. In practice, a value of 4 or
higher is seldom applied.
The previously mentioned “Pict33” tool can tackle a randomly given strength. For triplewise testing of the previously
given example, this tool calculates 43 test situations. Application of N=4 would deliver the maximum number of 108 test
situations.
ORTHOGONAL ARRAYS
The first example of pairwise testing deals with 3 parameters, each with 2 equivalence classes. If, for each parameter,
the equivalence classes are numbered, i.e. “1” and “2”, then the 4 test cases for pairwise testing are described by the
following 2-dimensional array:
|
Param-1
|
Param-2
|
Param-3
|
|
TC1
|
1
|
1
|
1
|
|
TC2
|
1
|
2
|
2
|
|
TC3
|
2
|
1
|
2
|
|
TC4
|
2
|
2
|
1
|
This is an example of an orthogonal array and is noted as L4(23). The meaning of the different
symbols here is:
4 = The number of rows (therefore the number of test cases that appear to be required)
3 = The number of columns (therefore the parameters that together form a test case)
2 = The maximum value in each column (therefore the number of equivalence classes of each parameter)
The interesting property of this array is that every combination of 2 columns contains all the possible combinations of
the values “1” and “2”. The term for this is that it is an orthogonal array of “strength 2”. This exactly fits the
purpose of pairwise testing, in which “all the combinations of equivalence classes of TWO random parameters” are
tested.
Another special property of orthogonal arrays is that they are balanced. That means that each combination of parameter
values occurs with equal frequency to any other combination of parameter values. This property distinguishes orthogonal
arrays from pairwise testing. With the test cases that are created through the application of pairwise testing, certain
equivalence classes usually occur more frequently than others do. With orthogonal arrays, all the equivalence classes
(even each combination of equivalence classes) occur with equal frequency.
For deeper testing than pairwise testing, an orthogonal array with a higher strength is necessary. For the testing of
all the combinations of equivalence classes of three random parameters, an orthogonal array of “strength 3” will be
required. Below is an orthogonal array of strength 3 for 4 parameters, each of which can have 2 values:
|
1
|
1
|
1
|
1
|
|
1
|
1
|
2
|
2
|
|
1
|
2
|
1
|
2
|
|
1
|
2
|
2
|
1
|
|
2
|
1
|
1
|
2
|
|
2
|
1
|
2
|
1
|
|
2
|
2
|
1
|
1
|
|
2
|
2
|
2
|
2
|
This array has the property that every combination of 3 columns contains all the possible combinations of the values 1
and 2, namely (1 1 1), (1 1 2), (1 2 1), (1 2 2), (2 1 1), (2 1 2), (2 2 1) and (2 2 2).
The notation for this orthogonal array is L8(24, 3), in which the number 3 indicates the strength
of the array. In the literature, there are various ways of noting orthogonal arrays. The most usual ways of notation
are:
-
L8(24, 3)
-
OA(8, 24, 3)
-
OA(8, 4, 2, 3)
If the value for strength is omitted, the default value of strength 2 is assumed.
All of the foregoing can be summarised in the following complicated definition: "An orthogonal array
LN(sk, t) is a 2-dimensional array of N rows and k columns consisting of elements that can assume
s values, whereby every combination of t columns contains all the combinations of the s values in equal
proportion."
An orthogonal array does not exist for every value of “s” and “k”. In practice, such a situation uses a ‘too big’
array, with the superfluous columns being ignored in its application.
So far, orthogonal arrays have been described in which the possible values for the elements of all the columns are
equal. There are also orthogonal arrays in which columns can have varying possible values. An example of this is
L8(24, 41, 2). The array of strength 2 contains 4 columns, each of which have 2
possible values, plus 1 column with 4 possible values. Such an array is set out below:
|
0
|
0
|
0
|
0
|
0
|
|
1
|
1
|
1
|
1
|
0
|
|
0
|
0
|
1
|
1
|
1
|
|
1
|
1
|
0
|
0
|
1
|
|
0
|
1
|
0
|
1
|
2
|
|
1
|
0
|
1
|
0
|
2
|
|
0
|
1
|
1
|
0
|
3
|
|
1
|
0
|
0
|
1
|
3
|
How do you get orthogonal arrays?
The creation of an orthogonal array is not simple. If there are several columns that can assume more than 2 values, it
is more or less impossible to do manually. Fortunately, there is extensive literature on the subject, including books,
articles and websites, with many examples and worked-out arrays that the tester can employ.
The book “Orthogonal arrays: Theory and Applications” [Hedayat, 1999] is generally accepted as the standard work on
orthogonal arrays.
One of the most extensive collections of orthogonal arrays on the Internet can be found on the site of N.J.A Sloane. An
Internet search for “orthogonal arrays” will undoubtedly lead to this and many other useful sites.
Deriving test cases with orthogonal arrays
The application of pairwise testing (and stronger variants) is simple, thanks to the available tools that quickly
generate the necessary test cases. Deriving the test cases using orthogonal arrays involves more work and is more
complicated, but gives the extra advantage of the “balanced test cases”: every combination of equivalence classes
occurs with equal frequency. The tester will have to consider whether this extra advantage is worth the additional
effort necessary.
For the enthusiasts, it is explained below how orthogonal arrays can be applied in order to derive a balanced set of
test cases for N-wise testing:
-
Determine the parameters of which the test case consists.
-
Determine the equivalence classes of each parameter.
-
Select the strength of the orthogonal array, based on the required strength of the test.
-
Find a fitting orthogonal array. An orthogonal array does not exist for every quantity of parameters and
equivalence classes. In that case, one has to be found that is ‘just a bit too big’. This can be done in 2 ways and
should then be used as follows:
-
There are too many columns (more columns than parameters). The relevant columns can simply be omitted. This
has no influence on the orthogonality of the array.
-
The maximum value of a column is too great. (The maximum value of “s” is greater than the number of
equivalence classes of the parameter.) Here, the rows that contain the too-great value may not be casually
omitted. These rows are necessary to realise the obligatory combinations of the other parameters. In this
case, a too-great value in the column should be construed as “don’t care value”. A random equivalence class
can therefore be selected
-
Translate the orthogonal array into test cases.
Example - In order to explain this, the same example is used as worked out with pairwise
testing, concerning the “book-ordering system”: Suppose that this system is to be tested with an average strength. The
5 steps for deriving the test cases proceed as follows:
Step 1: Determine the parameters of which the test case consists. There are 4 parameters: “Number of books”,
“Sum”, “Membership card”, “Ordering period”.
Step 2: Determine the equivalence classes of each parameter. The parameters are arranged in ascending order
according to the number of equivalence classes. This simplifies the search for a suitable orthogonal array (step 4).
Number of books : 1; 2-8; >8
Sum : <100; 100-250; >250
Ordering period : Weekday; Weekend; Public holiday
Membership card : None; Silver; Gold; Platinum
Step 3: Select the strength of the orthogonal array. Since the system is to be tested with average strength,
strength 2 is selected. For stronger testing, a higher strength can be selected. This mainly affects the search for a
fitting orthogonal array (step 4). Otherwise, the 5 steps remain unchanged in this technique.
Step 4: Find a fitting orthogonal array. There are 3 parameters with 3 equivalence classes and 1 parameter
with 4 equivalence classes. This means that an orthogonal array must be found that approximates as far as
possible:
LN(33, 41, 2)
Unfortunately, this orthogonal array does not exist. Therefore, one must be found that is just a bit bigger. The
following 2 orthogonal arrays could be considered:
-
L18(36, 61, 2) - This consists of 18 rows and 7 columns. Of the first 6 columns
(that can assume 3 values), 3 are superfluous and can be scrapped. The last column can assume 6 values, but of
those, only 4 are required for our test. The column therefore has 2 superfluous values that may be entered randomly
(the “don’t-matter values”).
-
L16(45, 2) - This consists of 16 rows and 5 columns. One column is superfluous and can be
scrapped. The first 3 columns of the remainder of the table then contain 1 possible value too many, which counts
among the “don’t-care values”.
The second array is selected, since it delivers the lowest number of required test cases. The
L16(45, 2) looks as follows:
|
1
|
1
|
1
|
1
|
1
|
|
1
|
2
|
2
|
2
|
2
|
|
1
|
3
|
3
|
3
|
3
|
|
1
|
4
|
4
|
4
|
4
|
|
2
|
1
|
2
|
3
|
4
|
|
2
|
2
|
1
|
4
|
3
|
|
2
|
3
|
4
|
1
|
2
|
|
2
|
4
|
3
|
2
|
1
|
|
3
|
1
|
3
|
4
|
2
|
|
3
|
2
|
4
|
3
|
1
|
|
3
|
3
|
1
|
2
|
4
|
|
3
|
4
|
2
|
1
|
3
|
|
4
|
1
|
4
|
2
|
3
|
|
4
|
2
|
3
|
1
|
4
|
|
4
|
3
|
2
|
4
|
1
|
|
4
|
4
|
1
|
3
|
2
|
Step 5: Translate the orthogonal array into test cases. The selected orthogonal array is now cut to size and then
filled in with the real values of the test parameters. The last column of the array is removed. The first 3 parameters have
only 3 possible values. For that reason, of the first 3 columns, the value “4” is replaced by a “~” , indicating that the
value does not matter. The array then looks as follows:
|
1
|
1
|
1
|
1
|
|
1
|
2
|
2
|
2
|
|
1
|
3
|
3
|
3
|
|
1
|
~
|
~
|
4
|
|
2
|
1
|
2
|
3
|
|
2
|
2
|
1
|
4
|
|
2
|
3
|
~
|
1
|
|
2
|
~
|
3
|
2
|
|
3
|
1
|
3
|
4
|
|
3
|
2
|
~
|
3
|
|
3
|
3
|
1
|
2
|
|
3
|
~
|
2
|
1
|
|
~
|
1
|
~
|
2
|
|
~
|
2
|
3
|
1
|
|
~
|
3
|
2
|
4
|
|
~
|
~
|
1
|
3
|
Through a clever selection from the “don’t-matter values”, a number of identical rows can be created: For the rows 4
and 15, the identical combination (1 3 2 4) can be selected and for the rows 10 and 16, the combination (3 2 1 3). With
this, two rows are dropped and, with these, two test cases. However, this reduction is not compulsory and will be left
out of consideration in the further process.
Finally, the test parameters should be allocated to the columns of the array and the values in the columns replaced by
an equivalence class. Which value is linked to which equivalence class is irrelevant, as long as they are consistently
applied. As a reminder, the parameters are repeated below with their equivalence classes summed up.
Number of books : 1; 2-8; >8
Sum : <100; 100-250; >250
Ordering period : Weekday; Weekend; Public holiday
Membership card : None; Silver; Gold; Platinum
In our example, the final result then looks as follows. A “~” still indicates that a random selection of the available
values may be made.
|
Number of books
|
Sum
|
Ordering period
|
Membership card
|
|
1
|
1
|
<100
|
Weekday
|
None
|
|
2
|
1
|
100-250
|
Weekend
|
Silver
|
|
3
|
1
|
>250
|
Public holiday
|
Gold
|
|
4
|
1
|
~
|
~
|
Platinum
|
|
5
|
2-8
|
<100
|
Weekend
|
Gold
|
|
6
|
2-8
|
100-250
|
Weekday
|
Platinum
|
|
7
|
2-8
|
>250
|
~
|
None
|
|
8
|
2-8
|
~
|
Public holiday
|
Silver
|
|
9
|
>8
|
<100
|
Public holiday
|
Platinum
|
|
10
|
>8
|
100-250
|
~
|
Gold
|
|
11
|
>8
|
>250
|
Weekday
|
Silver
|
|
12
|
>8
|
~
|
Weekend
|
None
|
|
13
|
~
|
<100
|
~
|
Silver
|
|
14
|
~
|
100-250
|
Public holiday
|
None
|
|
15
|
~
|
>250
|
Weekend
|
Platinum
|
|
16
|
~
|
~
|
Weekday
|
Gold
|
|
